package leecode.二叉树;

/**
 * @author wangxi created on 2021/5/30 20:06
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
 */
public class KthSmallestElementInBST {

    public static void main(String[] args) {
        String s = "8,6,10,5,7,9,11,null,null,null,null,null,null,null,null";
        TreeNode root = TreeNode.deserialize(s);

        KthSmallestElementInBST obj = new KthSmallestElementInBST();

        System.out.println(obj.kthNode(root, 3));
    }

    TreeNode res = null;
    int count = 0;
    TreeNode kthNode(TreeNode root, int k) {
        if (root == null || k <= 0) {
            return null;
        }
        count = k;
        help(root);
        return res;
    }

    private void help(TreeNode root) {
        if (root == null) {
            return;
        }
        help(root.left);
        // 不要在递归里面创建带状态的局部变量，有状态的局部变量值得变化统一放到方法的参数,比如不要使用k--
        // k--变为 k - 1放到参数上，但是此题不适合k-1的解法。
        // 因此采用全局变量的方法来代替k--，不受递归栈回退的影响
        // 递归回退是把所有值都会退到压栈前的值，k--也不例外，但是相对于k-1会出现意料之外的错误，因此别用k--

        // k--;
        count--;
        if (count == 0) {
            res = root;
            return;
        }
        help(root.right);
    }
}
